package topology_graph;

import java.util.LinkedList;

/**
 *
 * @author wxh
 */
public class Graph {

	private int v; // 顶点的个数
	public LinkedList<Integer> adj[]; // 邻接表

	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for (int i=0; i<v; ++i) {
			adj[i] = new LinkedList();
		}
	}

	public void addEdge(int s, int t) { // s先于t，边s->t
		adj[s].add(t);
	}

	public void topoSortByKahn() {
		// 统计每个顶点的入度
		int[] inDegree = new int[v];
		for (int i = 0; i < v; ++i) {
			for (int j = 0; j < adj[i].size(); ++j) {
				int w = adj[i].get(j); // i->w
				inDegree[w]++;
			}
		}

		// 统计入度为0的定点
		LinkedList<Integer> queue = new LinkedList();
		for (int i = 0; i < v; ++i) {
			if (inDegree[i] == 0) queue.add(i);
		}

		while (!queue.isEmpty()) {
			// 输出入度为0的定点
			int i = queue.remove();
			System.out.print("->" + i);
			for (int j = 0; j < adj[i].size(); ++j) {
				int k = adj[i].get(j);
				inDegree[k]--;
				if (inDegree[k] == 0) queue.add(k);
			}
		}
	}

	public static void main(String[] args) {

		Graph graph = new Graph(6);
		graph.addEdge(1,2);
		graph.addEdge(2,3);
		graph.addEdge(3,4);
		graph.addEdge(4,5);

		graph.topoSortByKahn();
	}

}